Паттерн матчинг revised

Все вы знаете, что некоторое время назад я вернулся из Турции и начал принимать
участие в новом проекте Cloudozer, написание Statically typed LLVM-based modern
functional language compiler with concurrency and gc for Xen applications and
raw hardware. К сожалению у меня нет много времени сейчас, так как нужно делать
ремонт и вообще говоря опять искать работу и новые проекты. Поэтому время на
компилятор остается все меньше и меньше, и я решил описать немного текущее
состояние дел. Возможно это меня вдохновит на еще один подход к этой задаче.

Что бы не ходить вокруг да около, вот например что этот алгоритм должен
матчить. Он используется в case конструкциях и multihead функциях, которые
впервые появились в HOPE. Обычно мультихед функции сразу представляют собой
матрицу M x N, но в case нужно еще разделять эти вхождения. Все это делается на
шагах компилятора еще до стадии унификации типов. Вообще говоря задача patter
maching compilation тесно связана с унификацией типов, так как внутри
приходится полагаться на информацию о типе для построения эффективного дерева
решения, а унификации типов нужно выводить тип cases паттернов как сумму типов.

case x of
    [1,2|tail] -> tail;
    [2,y] -> 2;
    [x,1,y|tail] -> 3;
    {{1,{_,2}},x,y} -> 4;
    {_,x,1,y} -> 5;
    {_,_} -> 6 * x + y;
    [{1,2,_},{x,y}] -> 7;
    _ -> :ok end.


Построение оптимального дерева решений таблицы правил является NP полной
задачей. Поэтому в компиляторах используются различные эвристики. Построение
этого дерева очень напоминает другой алгоритм: RETE алгоритм и его современный
модификации. Эта минимакс-задача построения самого компактного дерева сравнений
для данной матрицы правил за минимальное время.

Существует вот такой набор эвристик:

* Relevance (Baudined, MacQueen, 1985)
* Arity Factor (Baudinet, MacQueen, 1985)
* Small Defaults (Baudinet, MacQueen, 1985)
* Fewer Child Rules (Maranget, 1992, Ramsey, Fernandez, 1995)
* Left to Right (Sestoft, 1996, Moscow ML, OCaml, MLKit)
* Small Branching Factor (SML/NJ)
* Large Branching Factor (Cardelli, 1984)
* Leaf Edges
* Artificial Rule
* Right to Left Top-down

Их обычно различают на те которые проверяют значения всех ячеек
нормальнизированной M x N матрицы правил хотябы раз (эффективные) и те которые
этого не делают. В этом смысле алгоритмы MacQueen (1985), Laville (1991),
Maranget (1992), Sestoft (1996) -- эффективные, а алгоритмы Augustsson (1985),
Wadler (1987), Maranget (1994) -- нет. Вадлер это автор 6 или 7-й главы из
книги SPJ как писать миранды и хаскели.

Обычно эти эвристики работают с колонкой на каждом шаге и классифицируют ячейки
этой колонки по тиким категориям:

Heuristic         | Occurance in Column
----------------------------------------
Constructors      | N
Constants         | N or OccuranceMap
Vars              | -N
Wildcards         | -N

Здесь по сути я набросал приблизительные формулы уже по которым можно
характеризовать эти колонки. Это означает что ветвить деревья решений мы будем
на константах потому что по ним сразу можно разделить правила. Ну а переменные
мы обычно все запоминаем и переносим их имена на следующий шаг для того, что бы
использавать экстракторы из параметров или произведений и биндить BIND из
значения в тела функций которые будут вызываться при срабатывании этого правила.

Хороший компилятор должен отсекать все вызвы функций которые вызваны с
определенными типами на этапе компиляции и сразу делать переходы на
определенные правила совместимые с этими типами. Также, поскольку у нас
компилятор с удалением информации о типах, он должен вставлять специальную
инструкцию TAG для извлечение информации о порядковом номере суммы. Хотя
информации о типах мы удаляем но в рантайме мы должны различать
проиндексированные компоненты типов сумм.

Инструкции: SWITCH,ELEMENT,TAG,BIND. Элемент просто формирует адрес
извлекаемого значения для сравнения. Инструкция SWITCH которая скомпилируется а
аналогичную инструкцию LLVM, будет сравнивать эти значения, TAG будет узнавать
индекс типа члена суммы, а BIND ложить в стек для вызова результирующей
выбраной функции,

Простейший пример:

case l of
    {1,2,3} -> 1
    {1,x,4} -> 2
    {1,x,5} -> 3,
         x  -> 4


switch(element(1,L),
        {4,[bind(x,L)]},
        [{1,switch(element(2,L),
            {4,[bind(x,L)]},
            [{3,switch(element(3,L),
                {4,[bind(x,L)]},
                [{2,{1,[]}}])},
             {4,{2,[bind(x,element(2,L))]}},
             {5,{2,[bind(x,element(2,L))]}}])}]).

При построении этого дерева использовалась простейшая стратегия обхода
столбиков слева направо, которая написана у Вадлера.

caser x y ->
    case x of
        [1,2|tail] -> tail;
        [1,4]      -> 11;
        [2,3]   -> 20;
        [x,y,2] -> 21;
        [x,a,3|tail]    -> 31;
        [_,_,3,a,b,c,5] -> 32;
        [_,_,3,x,b,t,6] -> 33 end.

{switch,
    {tag,{var,x}},
    {fail},
    [{{cons,2},
      {switch,
          {shift,1},
          {switch,
              {shift,3},
              {fail},
              [{{int,3},
                {switch,
                    {shift,7},
                    {fail},
                    [{{int,6},
                      {ret,
                          {int,9,33},
                          {binds,[{t,{read,7}},{b,{read,6}},{x,{read,5}}]}}},
                     {{int,5},
                      {ret,
                          {int,8,32},
                          {binds,
                              [{c,{read,7}},{b,{read,6}},{a,{read,5}}]}}}]}},
               {{int,2},
                {ret,{int,6,21},{binds,[{y,{read,3}},{x,{read,1}}]}}}]},
          [{{int,2},{ret,{int,5,20},{binds,[]}}},
           {{int,1},
            {switch,
                {shift,2},
                {fail},
                [{{int,2},{ret,{var,3,tail},{binds,[]}}},
                 {{int,4},{ret,{int,4,11},{binds,[]}}}]}}]}}]}

Алгоритм находится сейчас вот в таком состоянии:

% List -- rows
% Exp -- Match Expression
% ColumnsOrder -- heuristic columns history
% DeepTrace -- history in tuples hierarchy

compile([],_,_,_,_) -> [];
compile(List,H,Exp,ColumnsOrder,DeepTrace) ->
    Column = heuristic(fun most_consts/1,List),
    io:format("Heuristic: ~p~n",[Column]),
    Fold = folda(Column,List),
%    io:format("~p Fold: ~p~n",[Column, Fold]),
    case [ group({Name},Fold) || Name <- [ctor,cvar] ] of
         [[],   Cvars] ->
compile(binds(Cvars,Column,DeepTrace),H,Exp,ColumnsOrder,DeepTrace);
         [Ctors,Cvars] ->
              switch({read,[Column|DeepTrace]},
                [ compile_ctor(C,Rows,Column,H,Exp,ColumnsOrder,DeepTrace) ||
{C,Rows} <- Ctors ],
                  compile_vars(Cvars,Column,H,Exp,ColumnsOrder,DeepTrace)) end.

Его нужно перписать так, что бы повременить с генераций кода а просто
переписать дерево программы в мультихед функции -- узлы дерева решений.

Матчинг Кортежей с именоваными компонентами и Бинарный матчинг

Еще хочется сказать о паттерн матчинге то, что не одними произведениями будешь
доволен нужно уметь матчить и произведения с именоваными компонентами:

case NamedTuple of
    {n=7,a=5} -> 1;
    {a=5,s=0} -> 2;
    {s=0,n=1} -> 3 end.

Совершенно другой алгоритм применяется для патчинга бинарей, которым так
славится Эрланг. Например вот такие конструкции:

case Binary of
    <42:8, X1>         -> 1;
      -> 2;
      -> 3 end.

Тут нужно всталять инструкции READ,SIZE,SCAN.

Паперы:
______________
[1] Peter Se stoft. ML patter n match compilation and partial evaluation. 1996
[2] Luc Maranget. Compiling Pattern Matching to good Decision Trees. 2008
[3] David MacQueen. Tree Pattern Matching for ML. 1958.
[4] Maxim Sokhatsky. L Pattern Matching Compilation. 2014.
[5] Kevin Scott and Norman Ramsey. When Do Match-Compilation Heuristics Matter? 2000